class XP

Definition

XP is defined as the class of parameterized problems that can be solved in time $n^{f(k)}$ for some parameter $k$ and computable function $f$

Notes

• it is the "slicewise" version of P
• XAC⁰ $\subseteq$ XP

References

1. https://en.wikipedia.org/wiki/Parameterized_complexity#XP
2. M. Bannach, F. Chudigiewitsch, and T. Tantau, “Existential Second-Order Logic Over Graphs: Parameterized Complexity,” Oct. 02, 2023, arXiv: arXiv:2310.01134. doi: 10.48550/arXiv.2310.01134.